Applying Bayesian optimization in problems wherein the search space is unknown is challenging. To address this problem, we propose a systematic volume expansion strategy for the Bayesian optimization. We devise a strategy to guarantee that in iterative expansions of the search space, our method can find a point whose function value within epsilon of the objective function maximum. Without the need to specify any parameters, our algorithm automatically triggers a minimal expansion required iteratively. We derive analytic expressions for when to trigger the expansion and by how much to expand. We also provide theoretical analysis to show that our method achieves epsilon-accuracy after a finite number of iterations. We demonstrate our method on both benchmark test functions and machine learning hyper-parameter tuning tasks and demonstrate that our method outperforms baselines.

Bayesian optimisation is a popular method for efficient optimisation of expensive black-box functions. Traditionally, BO assumes that the search space is known. However, in many problems, this assumption does not hold. To this end, we propose a novel BO algorithm which expands (and shifts) the search space over iterations based on controlling the expansion rate thought a \emph{hyperharmonic series}. Further, we propose another variant of our algorithm that scales to high dimensions. We show theoretically that for both our algorithms, the cumulative regret grows at sub-linear rates. Our experiments with synthetic and real-world optimisation tasks demonstrate the superiority of our algorithms over the current state-of-the-art methods for Bayesian optimisation in unknown search space.

Traditionally, BO assumes that the search space is known. However, in many problems, this assumption does not hold.

Traditionally, BO assumes that the search space is known. However, in many problems, this assumption does not hold.

Additional Feedback: Algorithm 2. X_t is never defined. I assumed that X_t is defined by Equation 2 like Algorithm 1. Authors mentioned the same computational budget for acquisition function optimization. What is the optimizer though? Constrained optimization of the acquisition function inside H_t (Equation 3) does not seem trivial. It isn't mentioned anywhere how the acquisition funciton was optimized.

The paper has been discussed after the rebuttal that the reviewers found useful and actionable (e.g., concerns about the confidence bound). The paper is recommended for acceptance. All reviewers have acknowledged that the paper is well motivated, well written and establishes a nice interplay between theory and a practical problem of interest.

Applying Bayesian optimization to expensive black-box problems needs to specify the bound of search space. However, when tackling a completely new problem, there is no prior knowledge to guarantee that the specified search space contains the global optimum. The paper proposes an approach to deal with this situation. In the approach, the user first specifies an initial search space; then the bound of search space automatically expands as the iteration proceeds; finally the algorithm will return a solution achieving \epsilon-accuracy. The key is how to expand the search space.

This paper proposes an algorithm to expand the search space for Bayesian optimization. The reviewers thought the work tackles an important problem and would be of interest to the community. The claims are well supported by empirical evidence and the paper is clearly written. There were concerns about the practicality of the method and that the work is a combination of well-known techniques. Because the paper presents a relatively novel approach and substantiates the claims with strong supporting evidence, it seems to be above the bar of acceptance.

Bayesian optimisation is a popular method for efficient optimisation of expensive black-box functions. Traditionally, BO assumes that the search space is known. However, in many problems, this assumption does not hold. To this end, we propose a novel BO algorithm which expands (and shifts) the search space over iterations based on controlling the expansion rate thought a \emph{hyperharmonic series}. Further, we propose another variant of our algorithm that scales to high dimensions. We show theoretically that for both our algorithms, the cumulative regret grows at sub-linear rates.

Applying Bayesian optimization in problems wherein the search space is unknown is challenging. To address this problem, we propose a systematic volume expansion strategy for the Bayesian optimization. We devise a strategy to guarantee that in iterative expansions of the search space, our method can find a point whose function value within epsilon of the objective function maximum. Without the need to specify any parameters, our algorithm automatically triggers a minimal expansion required iteratively. We derive analytic expressions for when to trigger the expansion and by how much to expand.